#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 998244353;
const int MAXN = 2000005;
ll a[65]; // 存储2^i % MOD的值，用于快速计算位权

// cnt[i][j]: i位二进制数中恰好有j个1的数字个数
// F[i][j]: i位二进制数中恰好有j个1的数字总和
ll cnt[65][65];
ll F[65][65];

ll solve(long long N, int K) {
  ll Ans = 0; // 最终结果
  ll sum = 0; // 当前已选高位的总和
  int j = 0;  // 当前已选的1的个数

  // 从最高位(60)到最低位(1)依次处理
  for (int k = 60; k >= 1; k--) {
    // 如果N的第k-1位是1
    if (N >> (k - 1) & 1) {
      // 贡献分为两部分：
      // 1. sum * cnt[k-1][K-j]: 已选高位的和 * 低位组合数
      // 2. F[k-1][K-j]: 低位自身的和
      Ans = (Ans + sum * cnt[k - 1][K - j] % MOD + F[k - 1][K - j]) % MOD;

      // 更新当前已选高位的和（加上当前位的权值）
      sum = (sum + a[k - 1]) % MOD;
      j++; // 已选1的个数增加
    }
    // 如果已经选了足够多的1，提前退出
    if (j >= K)
      break;
  }
  return Ans;
}

int main() {
  // 预处理2^i % MOD的值
  for (int i = 0; i <= 60; i++)
    a[i] = (1LL << i) % MOD;

  // 初始化组合数和数字和
  cnt[0][0] = 1; // 0位0个1的情况
  for (int i = 1; i <= 60; i++) {
    cnt[i][0] = cnt[i][i] = 1; // 边界条件：全0或全1
    F[i][0] = 0;               // 全0的和为0
    F[i][i] = a[i] - 1;        // 全1的和是2^i-1

    // 从低位1到高位i依次计算组合数和数字和

    for (int j = 1; j < i; j++) {
      // 组合数递推：选当前位为0或1
      cnt[i][j] = (cnt[i - 1][j] + cnt[i - 1][j - 1]) % MOD;

      // 数字和递推：
      // 1. 当前位为0：继承i-1位j个1的和
      // 2. 当前位为1：继承i-1位j-1个1的和，并加上当前位的贡献
      F[i][j] =
          (F[i - 1][j] + F[i - 1][j - 1] + cnt[i - 1][j - 1] * a[i - 1] % MOD) %
          MOD;
    }
  }

  int T;
  cin >> T;
  while (T--) {
    ll N;
    int K;
    cin >> N >> K;
    cout << solve(N, K) << endl;
  }

  return 0;
}